package 剑指Offer._5160;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/18 13:20
 * 数组中数字出现的次数
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * 算法：位运算
 * 将数组中的所有元素都异或，可以得到出现一次的两个数的异或
 * 找到异或结果中为 1 的那一位，来区分两个数字
 */
public class _56I {

    public int[] singleNumbers(int[] nums) {
        int tmp = 0;
        for (int num : nums) tmp ^= num;
        int idx = 31;
        for (; idx >= 0; idx--) if (((tmp >> idx) & 1) == 1) break;
        int[] ans = new int[2];
        for (int num : nums) {
            if (((num >> idx) & 1) == 0) ans[0] ^= num;
            else ans[1] ^= num;
        }
        return ans;
    }

}
